<script language="JavaScript">
//
// ***** Sokoban Solver *****
//
// Input of the program consists of (1) the map, (2) locations of player, boxes and goals; and
// (3) rules to reject bad locations of boxes (which is inside the function manual(r, c)).
//

// Markers of the map. Locations of the player, goals and boxes are not specified here.
//
// The following are used:
// O = Outside
// S = Space
// W = Wall
//
var O = -1;
var S = 0;
var W = 1;

// The map
var map = 
[
	[ W, W, W, W, W, W, W, W, W ],
	[ W, W, W, W, S, S, W, W, W ],
	[ W, W, W, W, S, S, W, W, W ],
	[ W, W, W, S, S, S, S, W, W ],
	[ W, W, W, S, S, S, S, W, W ],
	[ W, S, S, S, W, S, S, S, W ],
	[ W, W, S, S, S, S, S, S, W ],
	[ W, W, W, W, S, W, W, W, W ],
	[ W, W, W, W, W, W, W, W, W ]
];

// The rows and columns of the goal squares. They start from zero.
var goalR = [ 1, 1, 2, 3 ];
var goalC = [ 4, 5, 5, 6 ];

// The rows and columns of the boxes. They start from zero.
var boxR = [ 3, 4, 5, 5 ];
var boxC = [ 5, 4, 5, 6 ];

// The rows and columns of the player. They start from zero.
var playerR = 4;
var playerC = 3;

// Hash-table of visited positions
var numItems = 0;
var visited = new Object();

// Queue - data structure for the BFS code
var queue = new Array();

// Occupancy
var occ = new Array(map.length * map[0].length);

// Goal: is the square a goal square?
var goal = new Array(map.length * map[0].length);
for (var i = 0; i < goal.length; i++)
{
	goal[i] = 0;
}
for (var i = 0; i < goalR.length; i++)
	goal[ind(goalR[i], goalC[i])] = 1;

// Index: a number combining both row and column
function ind(r, c)
{
	return r * map[0].length + c;
}

// Is the square a wall?
function isWall(i, j)
{
	if (i < 0 || j < 0)
		return 1;
	if (i > map.length - 1 || j > map[0].length - 1)
		return 1;
	if (map[i][j] == W)
		return 1;
	return 0;
}

// Does the square contain a box?
function isBox(i, j)
{
	if (i < 0 || j < 0)
		return 0;
	if (i > map.length - 1 || j > map[0].length - 1)
		return 0;
	return occ[ind(i, j)];	
}

// Is the square a goal square?
function isGoal(i, j)
{
	if (i < 0 || j < 0)
		return 0;
	if (i > map.length - 1 || j > map[0].length - 1)
		return 0;
	return goal[ind(i, j)];	
}

// solved?
function solved()
{
	for (var i = 0; i < occ.length; i++)
		occ[i] = 0;
	for (var i = 0; i < boxR.length; i++)
		occ[ind(boxR[i], boxC[i])] = 1;

	for (var i = 0; i < goalR.length; i++)
	{
		if (occ[ind(goalR[i], goalC[i])] != 1)
			return false;
	}

	return true;
}

// Manual rules to discard bad positions.
// (r, c) = row and column of last moved box
function manual(r, c)
{
	// *** Put manual rules below ***
	//
	// *** Situations such as
	//   (1) Box at a non-goal corner square;
	//   (2) Two boxes next to each other near a wall but not all two on goal squares;
	//   (3) Three boxes surround a corner but not all three on goal squares;
	//   (4) Four boxes form a square but not all four on goal squares; and
	//   (5) # boxes next to a U-shape wall > # goal squares next to that wall
	// are rejected automatically. No need to worry about these cases here.
	//
	// Use the following variables/functions to aid judgement:
	// r : Row of the moved box
	// c : Column of the moved box
	// isWall(i, j): Is square (i, j) a wall?
	// isBox(i, j): Occupancy of square (i, j)
	// isGoal(i, j): Is square (i, j) a goal square?
	//

	// Two boxes next to each other with no hope of going to goal squares

	// Other rules
	if (c == 2 || r == 6)
		return false;

	return true;
}

// valid? (k = index of the moved box)
// quickly discard bad positions based on simple rules
function valid(k)
{
	// Mark the positions of boxes
	for (var i = 0; i < occ.length; i++)
	{
		occ[i] = 0;
	}
	for (var i = 0; i < boxR.length; i++)
		occ[ind(boxR[i], boxC[i])] = 1;

	// Row and column of the moved box
	var r = boxR[k];
	var c = boxC[k];

	// Performs a number of checking. Some forms of checking are provided for granted.

	var numB;
	var numW;
	var numG;

	// Automatic check 1: Rejects situations such as
	// (1) Two boxes next to each other near a wall but not all two on goal squares.
	// (2) Three boxes surround a corner but not all three on goal squares.
	// (3) Four boxes form a square but not all four on goal squares.
	//
	numB = isBox(r - 1, c - 1) + isBox(r - 1, c) + isBox(r, c - 1) + isBox(r, c);
	numW = isWall(r - 1, c - 1) + isWall(r - 1, c) + isWall(r, c - 1) + isWall(r, c);
	numG = isGoal(r - 1, c - 1) + isGoal(r - 1, c) + isGoal(r, c - 1) + isGoal(r, c);
	if (numB + numW == 4 && numG != numB)
		return false;

	numB = isBox(r - 1, c) + isBox(r - 1, c + 1) + isBox(r, c) + isBox(r, c + 1);
	numW = isWall(r - 1, c) + isWall(r - 1, c + 1) + isWall(r, c) + isWall(r, c + 1);
	numG = isGoal(r - 1, c) + isGoal(r - 1, c + 1) + isGoal(r, c) + isGoal(r, c + 1);
	if (numB + numW == 4 && numG != numB)
		return false;

	numB = isBox(r, c - 1) + isBox(r, c) + isBox(r + 1, c - 1) + isBox(r + 1, c);
	numW = isWall(r, c - 1) + isWall(r, c) + isWall(r + 1, c - 1) + isWall(r + 1, c);
	numG = isGoal(r, c - 1) + isGoal(r, c) + isGoal(r + 1, c - 1) + isGoal(r + 1, c);
	if (numB + numW == 4 && numG != numB)
		return false;

	numB = isBox(r, c) + isBox(r, c + 1) + isBox(r + 1, c) + isBox(r + 1, c + 1);
	numW = isWall(r, c) + isWall(r, c + 1) + isWall(r + 1, c) + isWall(r + 1, c + 1);
	numG = isGoal(r, c) + isGoal(r, c + 1) + isGoal(r + 1, c) + isGoal(r + 1, c + 1);
	if (numB + numW == 4 && numG != numB)
		return false;

	// Automatic check 2: Box at a corner position which is not a goal square.
	if (isGoal(r, c) != 1)
	{
		if (isWall(r - 1, c) == 1 && (isWall(r, c + 1) == 1 || isWall(r, c - 1) == 1))
			return false;
		if (isWall(r + 1, c) == 1 && (isWall(r, c + 1) == 1 || isWall(r, c - 1) == 1))
			return false;
	}

	// Automatic check 3: # boxes next to a U-shape wall > # goal squares next to that wall.

	// Check vertical
	var leftWall = isWall(r, c - 1) == 1;
	var rightWall = isWall(r, c + 1) == 1;
	numB = 1;
	numG = isGoal(r, c);
	for (var i = r - 1; isWall(i, c) != 1; i--)
	{
		numG += isGoal(i, c);
		numB += isBox(i, c);

		if (isWall(i, c - 1) != 1)
			leftWall = false;
		if (isWall(i, c + 1) != 1)
			rightWall = false;
	}
	for (var i = r + 1; isWall(i, c) != 1; i++)
	{
		numG += isGoal(i, c);
		numB += isBox(i, c);

		if (isWall(i, c - 1) != 1)
			leftWall = false;
		if (isWall(i, c + 1) != 1)
			rightWall = false;
	}
	if (numB > numG && (leftWall || rightWall))
		return false;

	// Check horizontal
	var upWall = isWall(r - 1, c) == 1;
	var downWall = isWall(r + 1, c) == 1;
	numB = 1;
	numG = isGoal(r, c);
	for (var i = c - 1; isWall(r, i) != 1; i--)
	{
		numG += isGoal(r, i);
		numB += isBox(r, i);

		if (isWall(r - 1, i) != 1)
			upWall = false;
		if (isWall(r + 1, i) != 1)
			downWall = false;
	}
	for (var i = c + 1; isWall(r, i) != 1; i++)
	{
		numG += isGoal(r, i);
		numB += isBox(r, i);

		if (isWall(r - 1, i) != 1)
			upWall = false;
		if (isWall(r + 1, i) != 1)
			downWall = false;		
	}
	if (numB > numG && (upWall || downWall))
		return false;

	return manual(r, c);
}

// Attempt to move one square in one of four directions (values allowed: 0,1,2,3).
// Return true if the move is valid; false otherwise.
function move(dir)
{
	// Movement vector
	var dr, dc;
	switch (dir)
	{
	case 0:
		dr = 0;
		dc = 1;
		break;
	case 1:
		dr = 1;
		dc = 0;
		break;
	case 2:
		dr = 0;
		dc = -1;
		break;
	case 3:
		dr = -1;
		dc = 0;
		break;
	default:
		alert("error");
		break;
	}

	// Check for the location of the player after the move.
	// The player can't go outside the map nor through the wall.
	if (playerR + dr < 0)
		return false;
	if (playerR + dr >= map.length)
		return false;
	if (playerC + dc < 0)
		return false;
	if (playerC + dc >= map[0].length)
		return false;
	if (map[playerR + dr][playerC + dc] == W)
		return false;

	// Check for the box (if it is there) at the player's new location.
	var k = -1;
	for (var i = 0; i < boxR.length; i++)
	{
		// Found the box. Now perform the check.
		if (boxR[i] == playerR + dr && boxC[i] == playerC + dc)
		{
			// That box should not go outside the map nor be pushed
			// to a wall.
			if (playerR + 2 * dr < 0)
				return false;
			if (playerR + 2 * dr >= map.length)
				return false;
			if (playerC + 2 * dc < 0)
				return false;
			if (playerC + 2 * dc >= map[0].length)
				return false;
			if (map[playerR + 2 * dr][playerC + 2 * dc] == W)
				return false;
			
			// Collide with another box?
			for (var j = 0; j < boxR.length; j++)
				if (boxR[j] == playerR + 2 * dr && boxC[j] == playerC + 2 * dc)
					return false;

			// That's it. There can only be one such box. Remember it
			// and break out of the loop.
			k = i;
			break;
		}
	}

	// Perform the move.
	playerR += dr;
	playerC += dc;
	if (k != -1)
	{
		boxR[k] += dr;
		boxC[k] += dc;

		// Undo if any of the boxes are in bad positions.
		if (!valid(k))
		{
			playerR -= dr;
			playerC -= dc;
			boxR[k] -= dr;
			boxC[k] -= dc;
			return false;
		}
	}

	return true;
}

// String representation of current positions of boxes and the player. The boxes are 
// first sorted in dictionary order of their locations, forming the displacements from
// the letter 'A'. The letters are joined together forming the required string
// representation.
function pos2Str()
{
	var r, c;
	var s = "";

	// Counting Sort
	for (var i = 0; i < occ.length; i++)
		occ[i] = 0;
	for (var i = 0; i < boxR.length; i++)
		occ[ind(boxR[i], boxC[i])] = 1;

	s += String.fromCharCode("A".charCodeAt() + playerR);
	s += String.fromCharCode("A".charCodeAt() + playerC);
	for (var i = 0; i < occ.length; i++)
		if (occ[i] == 1)
		{
			s += String.fromCharCode("A".charCodeAt() + i / map[0].length);
			s += String.fromCharCode("A".charCodeAt() + i % map[0].length);
		}

	return s;
}

// Restore positions of boxes (and the player) from string representation.
function str2Pos(s)
{
	playerR = s[0].charCodeAt() - "A".charCodeAt();
	playerC = s[1].charCodeAt() - "A".charCodeAt();

	for (var i = 0; i < goalR.length; i++)
	{
		boxR[i] = s[(i + 1) * 2].charCodeAt() - "A".charCodeAt();
		boxC[i] = s[(i + 1) * 2 + 1].charCodeAt() - "A".charCodeAt();
	}
}

// Returns the text representation of the current map. Only for debugging purposes.
function display()
{
	for (var i = 0; i < occ.length; i++)
		occ[i] = 0;
	for (var i = 0; i < boxR.length; i++)
		occ[ind(boxR[i], boxC[i])] = 1;

	var s = "";
	for (var i = 0; i < map.length; i++)
	{
		for (var j = 0; j < map[0].length; j++)
		{
			if (map[i][j] == W)
				s += "-5-";
			else
			{
				if (occ[ind(i, j)] == 1)
					s += "-8-";
				else if (i == playerR && j == playerC)
					s += "-1-";
				else
					s += "-0-";
			}
		}

		s += "\n";
	}

	return s;
}

// Search for the solution by performing a Breath-First Search (BFS). A technique
// in the textbook.
function BFS()
{
	var s1 = "";
	var s = pos2Str();

	// The starting point has nothing to store.
	visited[s] = "";
	queue.push(s);

	while (queue.length > 0)
	{
		s = queue.shift().toString();
		str2Pos(s);

		if (solved())
			return s;

		for (var dir = 0; dir <= 3; dir++)
			if (move(dir))
			{
				s1 = pos2Str();
				if (typeof(visited[s1]) == "undefined")
				{
					// Store enough information to allow retrieval
					// of path once a solution is found. Information
					// stored:
					// Direction of movement + String Representation of previous map
					visited[s1] = "" + dir + s;
					queue.push(s1);
					numItems++;

					if (solved())
						return s1;

					if (numItems >= 100000)
					{
						alert("Memory limit exceeded!");
						return "";
					}
				}

				// Undo the move
				str2Pos(s);
			}
	}

	return "";
}


var stack = new Array();
var finalPos = BFS();
if (finalPos != "")
{
	var s = finalPos;
	var d = [ "R", "D", "L", "U" ];
	
	// Once the level has been completed, go back the way the player has walked.
	// The order is reversed here, so a stack is used here.
	while (s != "")
	{
		s = visited[s].toString();
		if (s != "")
		{
			stack.push(d[parseInt(s[0])]);
			s = s.substr(1);
		}
	}
	
	// Read the stack to generate the move list.
	var n = 1;
	var sol = "";
	while (stack.length > 0)
	{
		sol += "" + n + ": " + stack.pop() + "\n";
		n++;
	}

	// Display the solution.
	alert("Solution (" + (n-1) + " steps):\n" + sol);
}
else
	alert("Solution not found!");

alert("Finished!");
</script>
